1. Field of the Invention
The present invention relates generally to renewal management for data items. A method, apparatus, system and computer readable medium are provided for managing renewal of a dynamic set of data items, each of which has an associated renewal deadline, in a data item management system.
2. Description of the Related Art
Cryptographic keys provide one example of data items which must be renewed from time to time. Cryptographic-key management represents a strategic control point. With the upcoming proliferation of symmetric and asymmetric keys used for encryption purposes in various applications such as tape or disk storage systems, communications and other applications, a global key management system with a generic and automated key-life-cycle management function becomes imperative. For instance, with the extension of encryption to the LTO-4 (Linear Tape-Open 4) magnetic storage technology, the number of encryption keys that must be managed explicitly will increase dramatically. Thousands of keys every month may have to be created, backed-up, served, archived, renewed, and possibly destroyed in compliance with current business policies and in a centrally-auditable fashion.
Aspects of the present invention address issues which include renewing, refreshing, rollover or rotation of keys. Current renewal management systems renew keys before expiry as required, key renewals being sufficiently spaced in time that no particular problem arises. Aspects of the present invention also address the issue that as the number of keys to be managed increases, and the time between generation and hence expiration of successive keys decreases, current renewal schemes become inadequate. Specifically, renewal deadlines for keys may be missed, as will be demonstrated below with reference to FIG. 1 of the accompanying drawings.
For example, when keys are generated, a renewal deadline (expiration time) is associated with each. If SN={k1, k2, . . . , ki, . . . , kN} is a set of N generated keys, and gi and ei denote the generation and expiration times of key ki, for i=1, 2, . . . , N, then the lifetime Ui of key ki is equal to the difference ei−gi, i.e. Ui=ei−gi. Assuming, without loss of generality, that the lifetime is constant for all keys, i.e. Ui=U, for i=1, 2, . . . , N, and also assuming that the duration of the process for renewing a key is Δ time units, for key ki to be renewed before it expires, its renewal should begin the latest at time τi, referred to as slack time, with τi=ei−Δ. Denoting by ri key ki 's renewal time, it should hold that ri≦τi. The later the renewal times, the lower the rate of key renewals, and therefore the lower the load on the processor engaged to perform the key renewals. Consequently, for performance enhancement, it is desirable that renewals occur as late as possible, i.e. ri should be as close to τi as possible.
A problem with simply following the above guidelines when scheduling key renewals is illustrated in FIG. 1. The lifetime of successive keys ki and ki+1 is indicated along the time axis. The renewal of ki and ki+1 are scheduled at ri=τi and ri+1=τi+1 respectively, but τi+1 falls in the renewal interval (τi, ei) for ki in which the processor will be renewing ki. Assuming for simplicity that the processor can renew at most one key at any given time, the processor will be busy during the renewal interval (τi, ei) so the renewal of ki+1 can only start after completion of renewal of ki, i.e. ri+1≧ei. This in turn implies that ki+1 will prematurely expire given that ri+1>τi+1. While the problem arises here because the renewal intervals for two keys ki and ki+1 overlap, note that the same problem can occur in the more general case where the processor is capable of simultaneously processing up to a given number of multiple keys. In the latter case, missed deadlines will become a problem where the renewal intervals for more than that number of keys overlap.
Another example where schemes for renewing data items face similar problems arises in key-encrypted data storage. In the context of a tape library, for example, a tape drive is generally shared by a number of tapes, which ranges from tens to hundreds, and this number will further increase in the future. According to the current encryption/decryption process, tapes store user data files which are each encrypted with a specific key. The tape drive is a scarce resource, spending most of its cycles on reading or writing encrypted data. When the expiration of any key is approaching, a key-life-cycle management function will identify it and will request the tape drive to first decrypt the associated data file, and then re-encrypt the data with a new (refreshed) key. This process can last quite some time, in the order of hours, depending on the length of the data file in question. Thus, if the number of asynchronous key renewals to be handled by the same tape drive increases sufficiently, the problem of missed deadlines can arise in a manner similar to the key scenario above.
Another data item renewal scenario where this problem will be faced is long-term data storage. If data must be preserved for long periods, the limited lifetime of data on a particular storage medium implies that data files must be periodically renewed by re-storing on the same medium or migration to a new medium. Where a sufficient number of files must be renewed by a read/write drive before their lifetime expires, the problem of missed renewal deadlines will arise as in the previous example.
An article entitled “Single machine scheduling to minimize weighted earliness subject to no tardy jobs,” S. Chand and H. Schneeberger, Eur. J. Oper. Res., vol. 34, pp. 221-230, 1988, addresses a “pull” type of production environment where jobs with known processing times and due dates are to be scheduled on a single machine such that they are not tardy and their total earliness is minimized. A job completed earlier than its due time may have to be stored, incurring inventory (holding) costs. In the context of data items such as keys, however, such costs do not arise, the issue being rather one of load on the processor or other renewal mechanism. The problem considered in this reference assumes that there is a given number of jobs to be scheduled and has been shown to be NP-hard. For the dynamic set of data items in the systems described above, solving the static scheduling problem each time a new data item is added to the set would be impractical, if not infeasible, because the problem is very complex (NP-hard) and the number of existing data items is likely to be large. Note that the dynamic programming approach developed in the foregoing reference can cope with at most 15 jobs.
Another approach is considered in the “just-in-time” (JIT) type of manufacturing systems where costs are connected not only with executing jobs too late, but also too early. The optimization problems are associated with goal functions, where there is a penalty for both tardiness and earliness of a job. The total weighted earliness/tardiness problem has been shown to be NP-hard (see “Sequencing with earliness and tardiness penalties: a review”, K. R. Baker and G. D. Scudder, Operations Research, vol. 38, 1990, pp. 22-36, 1990). Solving the problem amounts to establishing a sequence of jobs and its starting times. Because of an exponentially growing computation time, exact algorithms can be used only to solve instances where the number of jobs is small. For that reason, approximate algorithms have been proposed based on artificial intelligence methods. The issue of dynamic scheduling of arriving jobs such that the cost due to earliness is minimized has been considered in “Optimal stochastic sequencing with earliness and/or tardiness costs,” D. G. Pandelis and D. Teneketzis, in proceedings of the 32nd IEEE Conference on Decision and Control, vol. 4, pp. 3618-3623, December 1993. This is specifically concerned with non-idling scheduling strategies where the machine is not allowed to be idle while jobs wait to be processed. Hence jobs will be served immediately on arrival if the machine is idle. This process is incompatible with the objective of renewing data items as late as possible in the data item management systems addressed herein. Further examples of such known scheduling algorithms are described in: “Single-machine scheduling with early and tardy completion costs,” J. S. Davis and J. J. Kanet, Naval Research Logistics, vol. 40, pp. 85-101, 1993; and “Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed,” M. Azizoglu, M. Koksalan, and S. K. Koksalan, Journal of Operational Research Society, vol. 54, no. 6, pp. 661-664, June 2003. Again, however, these references address static systems and are specifically concerned with optimal scheduling for these systems.